﻿#include <iostream>
#include <queue>

using namespace std;

#define MAX(a, b) (a > b ? a : b)

static int maxCanHoldPoints(const int* arr, const size_t size, const size_t ropeLength)
{
    if (!arr || size == 0 || ropeLength == 0) return 0;

    int rEdge = arr[0] - 1;
    int lEdge = rEdge - ropeLength;
    int maxContains = 0;
    int rIndex = 0;
    int lIndex = 0;
    deque<int> dQueue;
    while (rEdge <= arr[size - 1])
    {
        if (rEdge == arr[rIndex])
        {
            dQueue.push_front(rIndex);
            ++rIndex;
        }

        if (lEdge > arr[lIndex])
        {
            dQueue.pop_back();
            ++lIndex;
        }

        maxContains = MAX(maxContains, dQueue.size());

        ++lEdge;
        ++rEdge;
    }

    return maxContains;
}

/**
 * 给定一个有序数组arr，代表数轴上从左到右有n个点arr[0],arr[1],arr[2]...arr[n-1],
 * 给定一个正整数L, 代表一根长度为L的绳子，求绳子最多能覆盖其中的几个点?
 *
 * 使用滑动窗口的思想, 时间复杂度: O(N)
 */
int main_RopeCoverPoints()
{
    int arr[] = {0,3,5,6,8,9,11,14,15,17,20,22};
    auto size = sizeof(arr) / sizeof(int);
    int ropeLength = 4;
    int maxPoints = maxCanHoldPoints(arr, size, ropeLength);
    printf("%d", maxPoints);
    return 0;
}